package hot100.双指针.单行到底.窗口.值累加;

/** 209-长度最小的子数组
/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0
 *
 * 求数组里 和为k的 连续的子数组们中 长度最小的那一个的 长度
 *
 */
public class subArraySum209 {

    public int subArraySum209(int[] nums, int k) {
        return 0;
    }
}

/**
 * 求出一个数组中连续子数组的和为k的个数
 *
 * 窗口
 */
class baseSlideTrain {

    //错误的滑动窗口实现
    /*public int subarraySumBySlide(int[] nums, int k) {
        int result = 0;

        int head = 0;
        for (int tail = 0; tail < nums.length; tail++) {
            int length = tail - head;
            int nowSum = 0;

            while (nowSum != k) {
                if (nowSum > k) {
                    head++;
                    nowSum -= nums[head];
                }
                else if (nowSum == k) {
                    result++;
                }
                else if (nowSum < k) {
                    for (int i = 0; i < length; i++) { nowSum += nums[head + i];}
                    break;
                }
            }

        }
        return result;
    }*/

    //正确的滑动窗口实现-用于全正数数组
    public int subArraySumSimple(int[] nums, int k) {

        /** (抽象推理)单独思考 head < tail OR head <= tail 没什么意义
         *   我们的目的性是
         *    -> 满足数组全体区间计算时 区间一定存在 即head-tail关系满足-一定要有数组长度来计算区间
         * **/
        int result = 0;


        /**head-tail支持重合、不重合表达 都不需要需要考虑开头结尾问题**/
        //不重合
        int head = -1; int sum = 0;
        for (int tail = 0; tail < nums.length; tail++) {
            sum += nums[tail];

          //while (sum > k && head <= tail) { //head与tail无需处理关系
            while (sum > k) {
                head++;
                sum -= nums[head];
            }
            if (sum == k) {
                result++;
            }
        }
        return result;

        /**重合**/
//        int result = 0;
//
//        int head = 0; int sum = 0;
//        for (int tail = 0; tail < nums.length; tail++) {
//            sum += nums[tail];
            //while (sum > k && head <= tail) {
//            while (sum > k) {             //已支持单个元素长度的处理 head与tail无需处理关系
//                sum -= nums[head];
//                head++;
//            }
//            if (sum == k) {
//                result++;
//            }
//        }
//        return result;
    }



    public static void main(String[] args) {
        baseSlideTrain test = new baseSlideTrain();
        System.out.println(test.subArraySumSimple(new int[]{3,4,7,8,4,2,8,8}, 7));
    }
}